package com.leetcode.tree.recursion;

/**
 * @author Dennis Li
 * @date 2020/10/25 14:35
 */
public class Connect_177 {
    static class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

    private Node last, nextStart;

    public Node connect(Node root) {
        if (root == null) return null;

        Node start = root;
        while (start != null) {
            last = null;
            nextStart = null;
            // 遍历第i层，基于已经建立好的链表关系进行遍历
            for (Node node = start; node != null; node = node.next) {
                // 同时建立第i+1层的链表
                if (node.left != null) {
                    link(node.left);
                }
                if (node.right != null) {
                    link(node.right);
                }
            }
            // 从下一层的第一个非空结点开始遍历
            start = nextStart;
        }

        return root;
    }

    // 连接结点
    private void link(Node node) {
        if (last != null) {
            last.next = node;
        }
        // 访问到第一个非空的节点会对next赋值
        if (nextStart == null) {
            nextStart = node;
        }
        last = node;
    }

}
